package 剑指Offer;

public class Offer63_股票的最大利润 {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int[] dp = new int[prices.length + 1];
        int min = prices[0];
        //dp[i] 代表 前 i 日的最大利润
        dp[0] = 0;//第0天的利润为0

        for (int i = 1; i <= prices.length; i++) {
            min = Math.min(min, prices[i - 1]);
            //注意这里：prices[i-1],就是第一天的价格，假如i=1,i-1=0;prices数组下标为0，就是第一个元素，也即第一天
            dp[i] = Math.max(dp[i - 1], prices[i - 1] - min);
        }

        return dp[prices.length];
    }
}
